/**
 * LeetCode133：克隆图
 * 给定无向连通图中一个节点的引用，返回该图的深拷贝
 * 图中的每个节点都包含它的值val(int)和其邻居的列表(list[Node])
 */

function Node(val, neighbors){
    this.val = val;
    this.neighbors = neighbors === undefined ? [] : neighbors;
}

/**
 * @description 通过深度优先遍历实现深拷贝
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph_1 = function (node){
    if (!node)return null;
    const visited = new Map();
    const dfs = (n) => {
        //拷贝节点
        const nCopy = new Node(n.val);
        //在visited中保存拷贝的节点，并将拷贝的新节点与原节点建立对应关系
        visited.set(n,nCopy);
        (n.neighbors || []).forEach(ne => {
            if (!visited.has(ne)){
                dfs(ne);
            }
            //为拷贝后的节点添加相邻节点
            nCopy.neighbors.push(visited.get(ne));
        });
    };
    dfs(node);
    return visited.get(node);
}

//时间复杂度：O(n)
//空间复杂度：O(n)

/**
 * @description 通过广度优先遍历实现深拷贝
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph_2 = function (node){
    if (!node)return null;
    const visited = new Map();
    visited.set(node,new Node(node.val));
    const q = [node];
    while(q.length){
        const n = q.shift();
        (n.neighbors || []).forEach(ne => {
            if (!visited.has(ne)){
                q.push(ne);
                visited.set(ne,new Node(ne.val));
            }
            visited.get(n).neighbors.push(visited.get(ne));
        });
    }
    return visited.get(node);
}